package com.zwj.interview.完全二叉树;

/**
 * @Author: Zwj
 * @Date: 2022/2/27 18:41
 */
public class 完全二叉树的节点个数 {

    public int countNodes(TreeNode root) {
        TreeNode left = root, right = root;
        int hl = 0;
        int hr = 0;
        //记录左子树的高度
        while (left != null) {
            left = left.left;
            hl++;
        }
        //记录右子树的高度
        while (right != null) {
            right = right.right;
            hr++;
        }
        //左右子树高度相同，说明是一颗满二叉树
        if (hl == hr) {
            return (int) Math.pow(2, hl) - 1;
        }
        //高度不同的话，就需要分别计算左子树和右子树的节点数量再加上root节点
        return 1 + countNodes(root.left) + countNodes(root.right);
    }



}